package leetcode_链表;

import general_class.ListNode;

/**
 * 排序链表
 * 算法：归并排序
 *
 * @author yezh
 * @date 2024/1/11 15:25
 */
public class _148 {

    public ListNode sortList(ListNode head) {
        return head == null || head.next == null ? head : divide(head);
    }

    ListNode divide(ListNode node) {
        if (node.next == null) return node;
        ListNode mid = mid(node);
        // 截断
        ListNode cur = node;
        while (cur != null && cur.next != mid) cur = cur.next;
        // cur 并定不为 null
        cur.next = null;
        ListNode n1 = divide(node);
        ListNode n2 = divide(mid);
        return merge(n1, n2);
    }

    ListNode dummy = new ListNode();

    ListNode merge(ListNode n1, ListNode n2) {
        dummy.next = null;
        ListNode cur = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                cur.next = n1;
                n1 = n1.next;
            } else {
                cur.next = n2;
                n2 = n2.next;
            }
            cur = cur.next;
        }
        if (n1 != null) cur.next = n1;
        else if (n2 != null) cur.next = n2;
        return dummy.next;
    }

    ListNode mid(ListNode node) {
        // 1 2 3 4 5 -> 3
        // 1 2 3 4   -> 3
        ListNode slow = node, fast = node;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
